package src.leetcode.dp.medium_1143;

public class longestCommonSubsequence {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.longestCommonSubsequence("abcde", "ace"));
    }
}

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();
        int [][]dp = new int [n][m];


        if(text1.charAt(0) == text2.charAt(0)) dp[0][0] = 1;
        for(int i = 1; i < n; i++){
            if(text1.charAt(i) == text2.charAt(0)) dp[i][0] = 1;
            else dp[i][0] = dp[i - 1][0];
        }
        for(int i = 1; i < m; i++){
            if(text1.charAt(0) == text2.charAt(i)) dp[0][i] = 1;
            else dp[0][i] = dp[0][i - 1];
        }

        for(int i = 1; i < n; i++) {
            for(int j = 1; j < m; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if(text1.charAt(i) == text2.charAt(j)) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1]+1);
                }
            }
        }

        return dp[n - 1][m - 1];
    }
}
